#!/usr/bin/env python
# -*- coding: utf8 -*-
'''Scan the directory tree and find all links (symbolic and hard),
and all files with the same content ('twins'). The last ones
can be changed to links saving space (in some cases).

Get a filename. Get the file type and size.
Skip special files. Skip too small files.
If it is a symlink, add it to the list of symlinks.
If there is no entry for the size in the dictionary, create one.
If the file is equal to any of the existing file lists of the size,
add the filename to the list.
Else add a new list containing only the filename.

The data structure is a dict of ordered lists of lists
(sets? No, too difficult to get one element of it):
{
 123: [['fileA',], ['fileB', 'fileC']],
 321: [['fileD']],
}
Here, 'fileB' and 'fileC' are twins.
'''

#import sys
import os.path
import types
import stat
import SortedBundledList as sbl
from optparse import OptionParser

BUFSIZE = 1*1024*1024
DEBUG = 0

def show(obj):
    '''Debugging tool: show everything about obj.'''
    res = 'show: %s\n' % str(obj)
    for _ii in dir(obj):
        res += '  show: %s: %s\n' % (_ii, str(getattr(obj, _ii)))
    return res

def log(msg, level=1, prefix=None):
    '''Report a warning, a notice, or a debug message.'''
    if level <= DEBUG:
        if prefix is None:
            print msg
        else:
            print prefix, msg

class FileName(unicode, sbl.Cmp):
    """A string containing a file name."""

    def __init__(self, name):
        try:
            sbl.Cmp.__init__(self)
            unicode.__init__(unicode(name, 'UTF-8', 'replace'))
        except UnicodeDecodeError:
            log('File %s has bad chars.' % str(name), 0, 'FileName.__init__')
            unicode.__init__(str(name))

class Skipped(sbl.SortedBundledList):
    """Files skipped due to errors e.g. removed. Elements of class FileName."""
    pass

class Small(sbl.SortedBundledList):
    """Files smaller than the -m limit. Elements of class FileName."""
    pass

class Symlinks(sbl.SortedBundledList):
    """Files which are symbolic links. Elements of class FileName."""

    def check(self, filename):
        '''Is this a symlink?'''
        return os.path.islink(filename)

class Specials(sbl.SortedBundledList):
    """Special files (FIFO, device etc). Elements of class FileName."""

    def check(self, filename):
        '''Is this a special file?'''
        return not (os.path.isdir(filename) or \
                    os.path.isfile(filename) or \
                    os.path.islink(filename))

class INode(sbl.SortedBundledList):
    """Names of the same file (same iNode). Elements of class FileName."""

    def check(self, filename):
        '''Is this a hardlink of these i-node?'''
        return os.path.samefile(self[0], filename)

    def cmp(self, filename):
        '''Compare the file system and the i-node'''
        _stat1 = os.stat(self[0])
        _stat2 = os.stat(filename)
        _result = cmp(_stat1.st_dev, _stat2.st_dev)
        if _result:
            return _result
        return cmp(_stat1.st_ino, _stat2.st_ino)

class Twins(object):
    """Hold the information about the files with the same content."""

    def __init__(self):
        self.fname = None      # current file name
        self.fdiscr = None     # current file descriptor
        self.stat = None       # result of lstat(self.fname)
        self.buf = None        # buffer with first part of the file
        self.twins = dict()    # dict list of lists: tw[size] = [[f0],[f1,f2]]
        self.hardlinks = dict()
        self.symlinks = Symlinks()
        self.specials = Specials()
        self.skipped = Skipped()
        self.smalls = Small()
        self.minsize = 1

    def fcmp(self, fname):
        """ int = twins.fcmp("file1")
        Compare current file to the given one, return -1, 0, 1 if content of
        fname is less, equal, greater than content of the current file.
        fname is a filename or a file-like object.
        """
        try:
            if self.fdiscr is None:
                self.fdiscr = open(self.fname, 'rb')
            if self.buf is None:
                self.buf = self.fdiscr.read(BUFSIZE)
            if isinstance(fname, types.StringTypes):
                fdiscr = open(fname, 'rb')
            else:    # it should be file object
                fdiscr = fname
            _b2 = fdiscr.read(BUFSIZE)
            _cm = cmp(self.buf, _b2)
            if _cm:
                return _cm
            self.fdiscr.seek(0)
            _b2 = self.fdiscr.read(BUFSIZE)
            while True:
                _b1 = self.fdiscr.read(BUFSIZE)
                _b2 = fdiscr.read(BUFSIZE)
                _cm = cmp(_b1, _b2)
                if _cm or not _b1 or not _b2:
                    return _cm
        except IOError:
            pass
        except StandardError, err:
            log("%s; files: %s, %s" % (err, self.fname, fname), 0, "fcmp:")
        return None

    def is_normal(self):
        "Check if current filename should be inserted into the object."
        try:
            self.stat = os.lstat(self.fname)
        except IOError:
            log('Cannot lstat file %s, skip.' % self.fname, 10, 'is_normal:')
            self.skipped.append(self.fname)
            return False
        if stat.S_ISDIR(self.stat.st_mode):
            log('Dir %s should not be here!' % self.fname, 0, 'is_normal:')
            return False
        if self.marksymlink() or \
           self.markspecial() or \
           self.marksmall() or \
           self.markhardlink():
            return False    # mark and skip
        if self.stat.st_size not in self.twins.keys():
            log('File %s is first of size %d.' % \
                    (self.fname, self.stat.st_size), 20, 'is_normal:')
            self.twins[self.stat.st_size] = [[self.fname]]
            return False
        return True

    def insert(self, fname):
        "Insert a filename into the object."
#        for code in ['ASCII', 'ISO8859-15', 'KOI8-R', 'UTF-16', 'UTF-8']:
        for code in ['ASCII', 'ISO8859-15', 'KOI8-R', 'UTF-16']:
            try:
                self.fname = unicode(fname, code)
                break
            except UnicodeDecodeError:
                log(code, 5)
                continue
        else:
            log('File %s has bad chars.' % str(fname), 1, 'Twins.insert:')
            self.fname = unicode(fname, 'ASCII', 'ignore')
        self.stat = None
        self.fdiscr = None
        self.buf = None
        if not self.is_normal():
            return    # skip special cases
        # binary search
        low = 0
        high = len(self.twins[self.stat.st_size]) - 1
        cur = low + (high - low) // 2
        while low <= high:
            _cm = self.fcmp(self.twins[self.stat.st_size][cur][0])
            if _cm is None:
                self.skipped.append(self.fname)
                return
            elif _cm == 0:
                self.twins[self.stat.st_size][cur].append(self.fname)
                return
            elif _cm < 0:
                high = cur - 1
            else:    # _cm > 0:
                low = cur + 1
            cur = low + (high - low) // 2
        self.twins[self.stat.st_size][cur:cur] = [[self.fname]]

    def markhardlink(self):
        '''Collect hardlink lists.'''
        if self.fname is None or self.stat.st_nlink == 1:
            return False
        if self.stat.st_size not in self.hardlinks.keys():
            self.hardlinks[self.stat.st_size] = [[FileName(self.fname)]]
            return False    # mark and include first link into the search
        for _jj in range(len(self.hardlinks[self.stat.st_size])):
            try:
                same = os.path.samefile(self.fname, \
                                     self.hardlinks[self.stat.st_size][_jj][0])
            except StandardError, err:
                log("Unexpected error: %s, %s %s %s %s" % \
                       (err, self.stat.st_size, _jj, self.fname, \
                        self.hardlinks[self.stat.st_size][_jj][0]), \
                    0, "markhardlink:")
                same = None
                continue
            if same:
                self.hardlinks[self.stat.st_size][_jj].append(\
                                                        FileName(self.fname))
                return True
        self.hardlinks[self.stat.st_size].append([FileName(self.fname)])
        return False

    def marksymlink(self):
        '''Collect symlink list.'''
        if os.path.islink(self.fname):
            log('File %s is a symbolic link.' % self.fname, 40, 'marksymlink:')
            self.symlinks.append(FileName(self.fname))
            return True
        return False

    def markspecial(self):
        '''Collect list of special files.'''
        if not (os.path.isdir(self.fname) or os.path.isfile(self.fname)):
            log('File %s is a special file.' % self.fname, 40, 'markspecial:')
            self.specials.append(FileName(self.fname))
            return True
        return False

    def marksmall(self):
        '''Collect list of small files.'''
        if self.stat.st_size < self.minsize:
            log('File %s is too small.' % self.fname, 30, 'marksmall:')
            self.smalls.append(FileName(self.fname))
            return True    # skip too small files
        return False

    def len(self):
        '''Count number of groups and total number of twins.'''
        group_counter = 0
        twin_counter = 0
        for _sz in self.twins.keys():
            for lst in self.twins[_sz]:
                if len(lst) > 1:
                    group_counter += 1
                    twin_counter += len(lst)
        return group_counter, twin_counter

    def __str__(self):
        res = ''
        for _sz in sorted(self.twins.keys()):
            for lst in self.twins[_sz]:
                if len(lst) > 1:
                    res += "%d(%d):\t%s\n" % (_sz, len(lst), '\n\t'.join(lst))
        return str(res)
#        return unicode(res, 'ASCII', 'replace')
#        return unicode(res, 'UTF-8', 'ignore')

def parse_args():
    '''Set a parser up and parse the args.'''
    parser = OptionParser()
    parser.add_option("-f", "--file", dest="filename",
                      help="write report to FILE", metavar="FILE")
    parser.add_option("-x", "--onefs",
                      action="store_true", dest="onefs", default=True,
                      help="do not descend to dirs on other filesystems")
    parser.add_option("-s", "--skip", default=[],
                      action="append", dest="skip", metavar="SKIP",
                      help="do not descend into the dir named SKIP")
    parser.add_option("-m", "--minsize", default=1L, metavar="SIZE",
                      dest="minsize", help="skip files less than SIZE bytes")
    parser.add_option("-d", "--debug", default=0, metavar="LEVEL",
                      dest="debug", help="set debug level to LEVEL")
    return parser.parse_args()

def main():
    '''Do the job, i.e. parse params, search, and print results.'''
    options, args = parse_args()
    if args is None or args == []:
        args = ['.']
    twins = Twins()
    if options.minsize:
        twins.minsize = eval('long(' + str(options.minsize) + ')')
    if options.debug:
        global DEBUG
        DEBUG = eval('int(' + str(options.debug) + ')')
    log(show(options), 50, 'main:')
    for arg in args:
        for root, dirs, files in os.walk(arg):
            for cat in options.skip:
                if cat in dirs:
                    dirs.remove(cat)
            if options.onefs:
                for cat in dirs:
                    if os.path.ismount(cat):
                        dirs.remove(cat)
            for fil in files:
                try:
                    log("root: %s, file: %s." % (root, fil), 10, 'main')
                    twins.insert(os.path.join(root, fil))
                except StandardError, err:
                    log("Error: %s; file: %s/%s." % \
                          (err, str(root), str(fil)), 0, 'main_0:')
                    continue
    print twins.skipped
    print twins.smalls
    print twins.specials
    print twins.symlinks
    print 'Hardlinks (' + str(len(twins.hardlinks)) + '):\n', twins.hardlinks
    print 'Twins' + str(twins.len()) + ':\n', str(twins)
    log(show(twins), 99, 'main:')

if __name__ == '__main__':
    main()
